﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.BinaryTreeCode
{
    //=========================迭代遍历（非递归）
    class IterativeTraversal
    {
        //=================力扣144 前序遍历（中左右）
        //给你二叉树的根节点root，返回它的节点值的前序遍历
        public IList<int> PreorderTraversal(TreeNode root)
        {
            Stack<TreeNode> st = new Stack<TreeNode>();
            IList<int> result = new List<int>();
            if (root == null)
                return result;
            st.Push(root);
            while (st.Count > 0)
            {
                TreeNode node = st.Pop();//中
                result.Add(node.val);
                if (node.right != null)
                    st.Push(node.right);//右（空节点不入栈）
                if (node.left != null)
                    st.Push(node.left);//左（空节点不入栈）
                //入栈先右后左，出栈的时候才会先左后右
            }
            return result;
        }

        //=================力扣94 中序遍历（左中右）
        public IList<int> InorderTraversal(TreeNode root)
        {
            IList<int> result = new List<int>();
            Stack<TreeNode> st = new Stack<TreeNode>();
            TreeNode cur = root;
            while (cur != null || st.Count > 0)
            {
                if (cur != null)//指针来访问节点，访问到最底层
                {
                    st.Push(cur);//将访问的节点放进栈
                    cur = cur.left;//左
                }
                else
                {
                    cur = st.Pop();//从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                    result.Add(cur.val);//中
                    cur = cur.right;//右
                }
            }
            return result;
        }

        //=================力扣145 后序遍历（左右中）
        public IList<int> PostorderTraversal(TreeNode root)
        {
            List<int> result = new List<int>();
            Stack<TreeNode> st = new Stack<TreeNode>();
            if (root == null)
                return result;
            st.Push(root);
            while (st.Count > 0)
            {
                TreeNode node = st.Pop();
                result.Add(node.val);
                if (node.left != null)
                    st.Push(node.left);//相对于前序遍历，更改一下入栈属性
                if (node.right != null)//空节点不入栈
                    st.Push(node.right);
            }
            result.Reverse();//结果反转就是左右中的顺序了
            return result;
        }


        //=========================================== 统一风格的迭代法
        //=================力扣144 前序遍历（中左右）
        //给你二叉树的根节点root，返回它的节点值的前序遍历
        public IList<int> PreorderTraversal_2(TreeNode root)
        {
            IList<int> result = new List<int>();
            Stack<TreeNode> st = new Stack<TreeNode>();
            if (root != null)
                st.Push(root);
            while(st.Count > 0)
            {
                TreeNode node = st.Peek();
                if(node != null)
                {
                    st.Pop();
                    if (node.right != null)
                        st.Push(node.right);
                    if (node.left != null)
                        st.Push(node.left);
                    st.Push(node);
                    st.Push(null);
                }
                else
                {
                    st.Pop();
                    node = st.Pop();
                    result.Add(node.val);
                }
            }
            return result;
        }

        //===================中序遍历（左中右）
        public IList<int> InorderTraversal_2(TreeNode root)
        {
            IList<int> result = new List<int>();
            Stack<TreeNode> st = new Stack<TreeNode>();
            if (root != null)
                st.Push(root);
            while(st.Count > 0)
            {
                TreeNode node = st.Peek();
                if (node != null)
                {
                    st.Pop();//弹出该节点，避免重复操作，然后再将右中左节点添加到栈中
                    if (node.right != null)
                        st.Push(node.right);//添加右节点，空节点不入栈
                    st.Push(node);//添加中节点
                    st.Push(null);//中节点访问过，但还没有处理，加入空节点作为标记
                    if (node.left != null)
                        st.Push(node.left);//添加左节点，空节点不入栈
                    //入栈先右后左，出栈的时候才会先左后右
                }
                else//遇到空节点时，才将下一个节点放进结果集合
                {
                    st.Pop();
                    node = st.Pop();
                    result.Add(node.val);
                }
            }
            return result;
        }

        //=================力扣145 后序遍历（左右中）
        public IList<int> PostorderTraversal_2(TreeNode root)
        {
            IList<int> result = new List<int>();
            Stack<TreeNode> st = new Stack<TreeNode>();
            if (root != null)
                st.Push(root);
            while(st.Count>0)
            {
                TreeNode node = st.Peek();
                if(node != null)
                {
                    st.Pop();
                    st.Push(node);
                    st.Push(null);
                    if (node.right != null)
                        st.Push(node.right);
                    if (node.left != null)
                        st.Push(node.left);
                }
                else
                {
                    st.Pop();
                    node = st.Pop();
                    result.Add(node.val);
                }
            }
            return result;
        }
    }
}
